#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int> > G_type; // edge list
bool find_alternative(const G_type& g, vector<int>& link, vector<int>& used, int s, bool inmatch=false)// in the same time reverse the path
{
	const vector<int>& adjs=g[s];
	int adj_got=-1;
	for(int i=0;i<adjs.size();i++)
	{
		int adj=adjs[i];
		if(!used[adj]) // we've got the path
		{
			adj_got=adj;
			break;
		}
		else
		{
			if(inmatch != (link[s]==adj)) // alternate
			{
				if(find_alternative(g, link, used, adj, !inmatch))
				{
					adj_got=adj;
					break;
				}
			}
		}
	}
	if(adj_got!=-1) // fine, get the path
	{
		// reverse the path
		if(link[s]!=adj_got)
		{
			link[s]=adj_got;
			link[adj_got]=s;
		}
		used[s]=1;
		used[adj_got]=1;
		
		return true;
	}
	else
		return false;
}

void bipartite_matching(const G_type& g, vector<int>& link)
{
	int N=g.size();
	fill(link.begin(), link.end(), -1);
	vector<int> used(N, 0);
	for(int i=0;i<N;i++)
	{
		if(!used[i])
			find_alternative(g, link, used, i);
	}
}

inline void link_node(G_type& g, int n1, int n2)
{
	g[n1].push_back(n2); g[n2].push_back(n1);
}

int main()
{
	{
		G_type g(6);
		link_node(g, 0,3);
		link_node(g, 0,4);
		link_node(g, 1,4);
		link_node(g, 1,5);
		link_node(g, 2,5);
		
		vector<int> link(6);
		bipartite_matching(g, link); // 0,3; 1,4; 2,5;
	}
	{
		G_type g(6);
		link_node(g, 0,3);
		link_node(g, 1,3);
		link_node(g, 2,3);
		link_node(g, 2,5);

		vector<int> link(6);
		bipartite_matching(g, link); // 0,3; 2,5;
	}
	{
		G_type g(6); // (0,1,2,3), (4,5)
		link_node(g,0,4);
		link_node(g,1,4);
		link_node(g,2,5);
		link_node(g,3,5);
		
		vector<int> link(6);
		bipartite_matching(g, link); // two
	}
	
	return 0;
}